package com.c2b.algorithm.leetcode.base;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * @author c2b
 * @since 2023/11/7 16:39
 */
public class LC0295 {
    static class MedianFinder {
        /*
            6个元素：大根堆-3 小根堆-3
            7个元素：大根堆-3 小根堆-4
         */
        // 大根堆：保存较多的一半。如果是偶数个，保存n/2，如果是奇数个，保存n/2 +1。
        PriorityQueue<Integer> heap1 ;
        // 小根堆：保存较少的一半。如果是偶数个，保存n/2，如果是奇数个，保存n/2。
        PriorityQueue<Integer> heap2;

        public MedianFinder() {
            heap1 = new PriorityQueue<>();
            heap2 = new PriorityQueue<>(Comparator.reverseOrder());
        }

        public void addNum(int num) {
            if (heap1.size() != heap2.size()) {
                heap1.add(num);
                heap2.add(heap1.poll());
            } else {
                heap2.add(num);
                heap1.add(heap2.poll());
            }
        }

        public double findMedian() {
            return heap1.size() == heap2.size() ? (heap1.peek() + heap2.peek()) / 2.0 : heap1.peek();
        }
    }

    public static void main(String[] args) {
        MedianFinder medianFinder = new MedianFinder();
        medianFinder.addNum(2);
        medianFinder.addNum(3);
        medianFinder.addNum(4);
        System.out.println(medianFinder.findMedian());

        MedianFinder medianFinder2 = new MedianFinder();
        medianFinder2.addNum(1);
        medianFinder2.addNum(2);
        System.out.println(medianFinder2.findMedian());
        medianFinder2.addNum(3);
        System.out.println(medianFinder2.findMedian());
    }
}
